#pragma once
#include "hConfig.h"
#include "hList.h"
#include "hInterval.h"

BEG_ENUM(hIntervalMapFindType)
{
	None,
	Overlap,
	Contain,
	Contained,
}
END_ENUM(hIntervalMapFindType, None, Overlap, Contain, Contained);

template <typename Key, typename Val, bool isConst>
struct _hIntervalMapIterator;
template <typename Key, typename Val>
class hIntervalMap;
template <typename Key, typename Val>
class hIntervalMapNode
{
	using ThisTy = hIntervalMapNode;
	using KeyTy = hInterval<Key>;
	using CKeyTy = const KeyTy;
	using Iter = typename hIntervalMap<Key, Val>::Iter;

	struct FillDebugParam;
	friend struct hIntervalMapNode::FillDebugParam;
	friend struct _hIntervalMapIterator<Key, Val, true>;
	friend struct _hIntervalMapIterator<Key, Val, false>;
	friend class hIntervalMap<Key, Val>;

	static hIntervalMapNode _nil;
	static hIntervalMapNode* _pNil;

	hIntervalMap<Key, Val>* _owner = NULL;
	hIntervalMapNode* _parent = _pNil;
	hIntervalMapNode* _left = _pNil;
	hIntervalMapNode* _right = _pNil;

	bool _red = true;
	uint8_t _type = 0;
	size_t _size = 0;
	KeyTy _keyIntv;
public:
	KeyTy _key;
	hList<Val> _valList;
	hIntervalMapNode(hIntervalMap<Key, Val>* pMap = NULL);
	~hIntervalMapNode();

	enum TraverseType
	{
		TraverseType_Pre,
		TraverseType_Mid,
		TraverseType_Post,
	};

	enum RotateType
	{
		RotateType_Left,
		RotateType_Right,
	};

	enum NodeType
	{
		NodeType_Nil,
		NodeType_Root,
		NodeType_Left,
		NodeType_Right,
	};

	template<typename... Args>
	std::pair<Iter, bool> emplaceCallback(const hInterval<Key>& k, Args... args);
	bool emplaceFixup();
	auto eraseCallback(const hInterval<Key>& k);
	auto eraseCallback(hListNode<Val>* pValNode);
	bool eraseFixup();
	Iter findByRankCallback(size_t r);
	bool checkCallback(const KeyTy& k, hEnum findTy);
	size_t findCallback(hList<Iter>& fdLst, const KeyTy& k, hEnum findTy);

	std::ostream& fillDebugCallback(std::ostream& os) const;
	const hIntervalMapNode* getNodeByHeight(uint8_t height, size_t idx) const;

	template <typename Callback>
	bool traverse(uint8_t type, Callback& cb);
	template <typename Callback>
	bool traverse(uint8_t type, Callback& cb) const;

	bool rotate(uint8_t type);

	hIntervalMapNode* getRoot();
	hIntervalMapNode* getUncle();
	hIntervalMapNode* getBrother();
	hIntervalMapNode* getMin();
	hIntervalMapNode* getMax();
	hIntervalMap<Key, Val>* getOwner();
	size_t getRank() const;
	size_t getSize() const { return _size; }
	uint8_t getNodeType() const;
	uint8_t calcHeightMax() const;

	bool operator==(const hIntervalMapNode& node) const { return _parent == node._parent && _left == node._left && _right == node._right; }
	bool operator!=(const hIntervalMapNode& node) const { return !operator==(node); }
private:
	bool rotateParent();
	bool rotateLeft();
	bool rotateRight();

	template<typename... Args>
	std::pair<Iter, bool>  emplaceNode(hIntervalMapNode* pNode, const hInterval<Key>& k, Args... args);
	bool checkNeedEmplaceFixup();
	bool emplaceFixupCase1(hIntervalMapNode* pGrandpa, hIntervalMapNode* pUncle);
	bool emplaceFixupCase2(hIntervalMapNode* pParent);
	bool emplaceFixupCase3();

	auto eraseNode(hIntervalMapNode* pNode, const hInterval<Key>& k);
	bool transplant(hIntervalMapNode* pNode);
	bool eraseFixupCase1(hIntervalMapNode*& pBrother);
	bool eraseFixupCase2(hIntervalMapNode* pBrother);
	bool eraseFixupCase3(hIntervalMapNode*& pBrother, bool isLeft);
	bool eraseFixupCase4(hIntervalMapNode* pBrother, bool isLeft);

	void setType(uint8_t type) { if (_type) _type = type; }
	void calcSize() { _size = _valList.size() + _left->_size + _right->_size; }
	void calcIntr();

	hIntervalMapNode* getNextNode();
	const hIntervalMapNode* getNextNode() const;
};

#include "hIntervalMapNodeImpl.h"